﻿/*
给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

	1
   / \
  2   2
 / \ / \
3  4 4  3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

	1
   / \
  2   2
   \   \
   3    3
说明:

如果你可以运用递归和迭代两种方法解决这个问题，会很加分。
*/

#include "AllInc.h"

struct TreeNode 
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
	bool isSymmetric(TreeNode* root) 
	{
		if (NULL == root)
		{
			return true;
		}

		return isImagie(root->left, root->right);
	}

	bool isImagie(TreeNode* left, TreeNode* right)
	{
		if (left == NULL && right == NULL)
		{
			return true;
		}
		else if (left && right)
		{
			if (left->val != right->val)
			{
				return false;
			}

			return isImagie(left->left, right->right) && isImagie(left->right, right->left);
		}
		else
		{
			return false;
		}
	}
};

//int main()
//{
//	TreeNode n1(1);
//	TreeNode n21(2);
//	TreeNode n22(2);
//	TreeNode n31(3);
//	TreeNode n32(4);
//	TreeNode n33(4);
//	TreeNode n34(3);
//	n1.left = &n21;
//	n1.right = &n22;
//	n21.left = &n31;
//	n21.right = &n32;
//	n22.left = &n33;
//	n22.right = &n34;
//
//	Solution s;
//	auto result = s.isSymmetric(&n1);
//
//	return 0;
//}